This invention relates to the field of optimal control and more particularly to distributed sensing and cooperative control systems and methods for distributed optimization.
When multiple agents or processors are controlled to cooperatively achieve an objective, the cooperative performance of the collective can be more effective than the performance of a collection of independent agents or processors. Multiple agents or processors in a collective can collect and share information to enhance each one""s strategy to achieve the objective. Independent and distributed sensing and sharing of information among multiple autonomous or semi-autonomous cooperating collective members as well as cooperative control for each member of the collective can improve the search strategy to achieve the objective without sacrificing efficiency or imposing an undue communication or processing burden.
Areas that are particularly applicable are the use of multiple agents in surveillance and inspection, in following and tagging, in locating and identifying targets, and in other applications which can remove humans from tedious or potentially dangerous activities. Examples of a need for distributed optimization and cooperative control include using small autonomous robotic vehicles in the above application areas. A particular example is a search and tag operation to find the source of a time-varying chemical plume, temperature source, radiation source, or light source. Interest in the above application areas is growing due to recent advances in microelectronics and sensors. These advances include small, low power CCD cameras; small microprocessors with expanded capabilities; autonomous navigation systems using global positioning systems; and several types of small sensors; which can be used in conjunction with inexpensive, easy to fabricate, autonomous vehicles, built in quantity and cooperating in an optimal search mission.
Examples of distributed optimal searches within an n-dimensional space include cooperative software agent cyberspace searches (for example, searches using a network of interconnected computers to optimize a specified search objective, searches using the parallelization of a multiple-processor computer such as a Paragon computer, searches in a multiprocessing computer environment to find an optimal solution to a time-independent or time-dependent maximization or minimization problem), and the use of a computer to optimally solve problems such as time-varying functional surfaces and two-point boundary value problems.
Optimization Systems
Park and Vadali teach a multiple shooting method to solve trajectory optimization two-point boundary-value problems. In the multiple shooting method, a trajectory is divided into subintervals, and parameters within each subinterval are found which optimize the overall trajectory, subject to matching conditions at the boundaries between the subintervals. Park and Vadali do not teach cooperative utilization of information to improve and update search control strategies. See Park and Vadali, xe2x80x9cTouch Points in Optimal Ascent Trajectories with First-Order State Inequality Constraints,xe2x80x9d Journal of Guidance, Control, and Dynamics, Vol. 21, No. 4, pp. 603-610, July-August 1998.
The multiple shooting method is similar to a multilevel optimization approach where units, such as subsystems or agents, in a process are uncoupled and optimized individually, while subject to equality constraints requiring a match of certain conditions between the units. While the multilevel optimization approach works well in certain applications, it does not work where uncoupled units possess a saddle point indeterminate as a true global minimum or a local saddle point. See Avery and Foss, xe2x80x9cA Shortcoming of the Multilevel Optimization Technique,xe2x80x9d AlChE Journal, Vol. 17, No. 4, pp. 998-999, July 1971.
Jennings et al. teach cooperative behaviors and provision of additional force or dexterity within teams of robotic agents to accomplish a rescue task. Jennings et al. do not teach cooperative behaviors during a search task. See Jennings et al., xe2x80x9cCooperative Search and Rescue with a Team of Mobile Robots,xe2x80x9d IEEE International Conference of Advanced Robotics, Monterey, Calif., 1997.
Search Control
Cooperative search applications to achieve an objective result in a need for a controller for multiple agents or processors in a collective to collect and share information to make better decisions in order to achieve the objective. Accordingly, there is an unmet need for a distributed search system suitable for multiple autonomous or semi-autonomous cooperating collective members that can be used to provide independent and distributed sensing and sharing of information as well as cooperative control for each member of the collective to improve its search strategy to achieve the objective.
The present invention provides a distributed search system suitable for controlling multiple agents to search an area for an objective utilizing a sensor, a communicator, and a cooperative controller, generating an update strategy to control each agent determined from a sensor reading and a cooperative approximation to the search area. The search area can comprise a physical geography or a cyberspace search area. Robotic vehicles, computer processors, and software agents are all suitable for use with the present invention.
The present invention teaches a new search method for controlling multiple agents or multiple processors to search an area for an objective. The objective can be any combination of the following: chemical sources, temperature sources, radiation sources, light sources, evaders, trespassers, explosive sources, time dependent sources, time independent sources, function surfaces, maximization sources, minimization sources, and optimal control of a system (for example, a communication system, an economy, a crane, a multi-processor computer). The search method utilizes sensor and location input and searches the area until an optimization condition for the objective is met.